package 剑指offer.贪心与动态规划;

/*
    0 ~ 25 对应着 a ~ z
    输入 12258 要输出有多少种不同的翻译方法

    TODO 要是要求你输出全部的结果呢？不只是输出有几种办法
 */
public class 第46题把数字翻译成字符串 {

    /*
    自顶向下分析会发现数据出现出现大量的重复现象
    一旦发现这个特征，一定要使用自底向上的递归解决
        参考解析之后，发现此题类似于斐波那契数列。
        可以按照自底向上的办法处理

        对于 12258 从最后面开始，设 f(i)为从 i 开始寻找不同的翻译办法
        f(4)表示的是数字 8，只有一种翻译方法
        f(3)表示的是数字 5，有 5、8 一种方法
        f(2)有 2、5、8；25、8；两种方法
        f(1)有三种方法

        于是有 f(i) = f(i+1) + f(i+2) * in(i, i+1)

        in(i, i+1) 表示第 i 位和第 i+1 位拼起来的值在 0~25 之间

        可以发现越靠前的计算结果越依赖之前计算的结果。
        也就是可以存储基本的解然后得到最终的解，所以不能用递归，直接使用循环即可

     */
    public static int translateNumToString(int number) {
        String s = number + "";
        int count = 0;
        int[] tmpCount = new int[s.length()];
//        for (int i = s.length() - 1; i >= 0; i--) {
//            count = 0;
//            if (i < s.length() - 1)
//                count = tmpCount[i + 1];
//            else
//                count = 1;
//            if (i < s.length() - 1) {
//                int front = Integer.valueOf(String.valueOf(s.charAt(i)));
//                int back = Integer.valueOf(String.valueOf(s.charAt(i + 1)));
//                int size = front * 10 + back;
//                if (size >= 10 && size <= 25) {
//                    if (i < s.length() - 2)
//                        count += tmpCount[i + 2];
//                    else
//                        count += 1;
//                }
//            }
//            tmpCount[i] = count;
//        }
        return tmpCount[0];
    }

    public static void main(String[] args) {
//        System.out.println(translateNumToString(1226258031));
        System.out.println(GetTranslationCount(12258));

//        System.out.println('5' - '0');
    }

    /**
     * 自下而上分析后，发现出现几起重复计算的例子，
     * 因此使用动态规划，从最小的问题开始 ：
     *
     * f(r)表示以r为开始（r最小取0）到最右端所组成的数字能够翻译成字符串的种数。
     *
     * 对于长度为n的数字，f(n)=0,f(n-1)=1,求f(0)。【从0开始计数】
     * 递推公式为 f(r-2) = f(r-1)+g(r-2,r-1)f(r)；
     * 其中，如果r-2，r-1能够翻译成字符，则g(r-2,r-1)=1，否则为0。
     * 因此，对于 12258：
     * f(5) = 0
     * f(4) = 1
     * f(3) = f(4)+0 = 1
     * f(2) = f(3)+f(4) = 2
     * f(1) = f(2)+f(3) = 3
     * f(0) = f(1)+f(2) = 5
     *
     * @param number
     * @return
     */
    public static int GetTranslationCount(int number) {
        String str = number + "";
        char[] s = str.toCharArray();
        if (s.length == 0)
            return 0;
        if (s.length == 1)
            return 1;
        // 先存储基本解
        int f1 = 0;
        int f2 = 1;
        int g = 0;
        // 然后从后往前开始寻找最终解
        // s.length - 2 表示从倒数第二个数字开始，也就是例子中的 5，因为 8 的解已经保存了
        for (int i = s.length - 2; i >= 0; i--) {
            // 若i和i+1组成的数字在0到25之间，把g设置为1
            if ((s[i] - '0') * 10 + (s[i + 1] - '0') < 26)
                g = 1;
            else
                g = 0;
            int temp = f2;
            // f1 代表的是 f(i+2)
            // f2 代表的是 f(i+1)
            f2 = f2 + g * f1;
            f1 = temp;
        }
        return f2;
    }


}
